//: [Previous](@previous)

//: LeetCode练习

import Foundation

/*
 如何用快排思想在O(n)内查找第K大元素？
 */

func findArray(_ arr: [Int], k: Int) -> Int {
    
    let pivot = arr.count/2
    
    min(3, 2)
    
    return 2;
}


/*
 寻找和为特定值的两个数,并输出他们的下标
 */
func twoSum(to target: Int, from nums: inout [Int]) -> [(Int, Int)] {
    //把数组以dict存储的容器
    var dict = [Int : Int]()
    //存储特定值的下标
    var arr = [(Int, Int)]()
    for i in 0..<nums.count {
        let current = nums[i]
        let other = target - current
        if let otherIdx = dict[other] {
            arr.append((otherIdx, i))
        }
        dict[current] = i
    }
    return arr
}
var arr2 = [1,3,5,13,7,8,4,9]
twoSum(to: 10, from: &arr2)



// MARK: - 数组相关

/*
 删除排序数组中的重复项
 1. 使用Set获取到不重复的数量
 2. 遍历两两对比，移除多余元素
 */
func removeDuplicates(_ nums: inout [Int]) -> Int {
    let count = Set(nums).count
    while nums.count != count {
        for i in 0..<nums.count - 1 {
            if nums[i] == nums[i + 1] {
                nums.remove(at: i)
                break
            }
        }
    }
    print(nums)
    return nums.count
}

/*
 旋转数组
 */
func rotate(_ nums: inout [Int], _ k: Int) {
    for _ in 0..<k {
        let last = nums.last!
        nums.insert(last, at: 0)
        nums.removeLast()
    }
}

/*
 存在重复的元素
 1. 排序
 2. 遍历，检测相邻的元素是否有相等
 */
func containsDuplicate(_ nums: [Int]) -> Bool {
    if nums.count == 0 {
        return false
    }
    let sortedArr = nums.sorted()
    for i in 1..<sortedArr.count {
        if sortedArr[i] == sortedArr[i-1] {
            return true
        }
    }
    return false
}
//containsDuplicate([2,3,4,5,6,7,3])


/*
 只出现一次的数字
 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 1. 排序
 2. 遍历，考虑这个数字在最后一个元素的情况
 */
func singleNumber(_ nums: [Int]) -> Int {
    let arr = nums.sorted()
    for i in 0..<arr.count where i%2 == 0{
        //如果single是在最后一位
        if i == arr.count - 1 {
            return arr[i]
        }else{
            if arr[i] != arr[i+1] {
                print(arr[i],arr[i+1])
                return arr[i]
            }
        }
    }
    return 0
}
let arr = [3,3,2,2,7,5,5]
//singleNumber(arr)


/*
 两数之和
 */
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for i in 0..<nums.count {
        for j in i+1..<nums.count {
            if nums[i] + nums[j] == target {
                return [i,j]
            }
        }
    }
    return [Int]()
}

//两个数组的交集
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    var nums = [Int]()
    var dic = [Int : Int]()
    for num1 in nums1 {
        if let _ = dic[num1] {
            dic[num1]! += 1
        }else{
            dic[num1] = 1
        }
    }
    for num2 in nums2 {
        if let count = dic[num2] {
            
        }
    }
    
    return nums
}
intersect([1,2,2,1], [2])




//翻转字符串
func reverseString(_ s: inout [Character]) {
    
    var characters = [Character]()
    
    
    var left = 0
    var right = s.count - 1
    while left < right {
        s.swapAt(left, right)
        left += 1
        right -= 1
    }
}

let str = "abc"
var characters = [Character]()
for c in str {
    characters.append(c)
}

print(characters)





//整数翻转
func reverse(_ x: Int) -> Int {
    var temp = x
    var new = 0
    while temp != 0 {
        //取出最后一个数字
        let lastNum = temp%10
        temp /= 10
        print("\(new*10),\(lastNum)")
        new = new * 10 + lastNum
//        print(lastNum)
    }
    return new
}
reverse(1234)


func removeDuplicates2(_ nums: inout [Int]) -> Int {
    let set = Set(nums)
    nums = Array(set)
    nums.sort()
    print(nums)
    return nums.count
}

var nums = [0,0,1,1,1,2,2,3,3,4,7,8]
//removeDuplicates(&nums)
removeDuplicates2(&nums)




class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        var digits = digits
        var carry = 1
        for i in (0..<digits.count).reversed() {
            // 末尾元素值 +1
            digits[i] += carry
            if digits[i] < 10 {
                carry = 0
                break
            } else {
                digits[i] = 0
                carry = 1
            }
        }
        if carry == 1 {
            digits.insert(1, at: 0)
        }
        return digits
    }
}

